# -*- coding: utf-8 -*-            
# @Time : 2023/3/15 22:29
# @Author  : lining
# @FileName: 快排.py
"""
a = [1,3,5,7,9,2,4,6,8,0,11]
选一个基准点，先从最右边往左遍历，找到第一个比基准点小的数，交换。然后从最左边开始找第一个比基准点大的数，交换，再从右边开始
一直到两个指针重叠。这时第一个基准点就到了他该在的位置，然后基准点左边右边的数分别做排序。
"""
a = [1,3,5,7,9,2,4,6,8,0,11]


def quick_sort(begin, end):
    """
    :param basepoint: 基准点
    :param begin: 开始点
    :param end: 结束点
    :return:
    """
    if end<=begin:
        return
    start = begin
    final = end
    basepoint = round((start+final)/2)
    base_point = a[basepoint]
    while begin!=end:
        # 右边--
        right = a[end]
        # 右边的数大于基准值，继续下一个数
        if right>=base_point:
            end = end-1
            continue
        # 右边的数小于基准值，交换
        if right<base_point:
            a[end],a[basepoint] = base_point,right
            basepoint = end
        # 左边++
        while begin!=end:
            left = a[begin]
            # 左边小于等于基准值，++
            if left<=base_point:
                begin = begin+1
                continue
            # 左边大于基准值，交换
            a[basepoint],a[begin] =left, base_point
            basepoint = begin
            break
    print(a)
    # 左边排序
    quick_sort(start,basepoint-1)
    # 右边排序
    quick_sort(basepoint+1, final)


quick_sort(0,10)


